In the context of internetworking, routing is the coordinated transfer of information from a source to a destination via hardware known as a router. Routing occurs at Layer 3, the network layer of the Open System Interconnection (OSI) reference model of the International Society for Standardization (ISO). The OSI reference model is a conceptual model composed of seven layers, each specifying particular network functions. The two lowest layers (layers 1 and 2) of the OSI model, namely the physical and data link layers are implemented in both hardware and software. Layer 3 and those above are generally implemented only in software.
Using ISO terminology, network devices may be classified as follows. Those devices with the capability to forward packets between sub networks are referred to as intermediate systems (ISs). In contrast, network devices without such capabilities are called end systems (ESs). Intermediate systems may be classified as intradomain ISs, i.e., those which can communicate within routing domains, and interdomain ISs which can communicate both within and between routing domains. A routing domain, or autonomous system, can be considered to be a part of an internetwork, which is regulated under common administrative authority.
A key component of routing is determination of optimal routing paths for data packets. Thereafter a second component, which may be referred to as “forwarding”, comprises transporting packets through the internetwork. Determination of optimal routing paths relies on one or more routing protocols to provide and update a routing database for each router or peer in a network. Depending on the particular routing protocol(s) used, various metrics are involved in building the routing database. Metrics that may be used by various routing protocols, either singly or as components of hybrid metrics, including: bandwidth, cost, path length, reliability, and load. Such metrics are well known in the art.
Routing protocols are used to determine best routes for transporting packets through an internetwork. Routing in a network can be classified as either dynamic or static. Static routing is accomplished by using table mappings, which are entered by a user (e.g. network administrator) prior to routing, and are only changed by user input. Dynamic routing is accomplished by routing protocols that adjust to changing network conditions in response to incoming route update information. As a result, routes are recalculated, new routing update messages are sent out to peer routers, and updated routing databases are constructed. Routing protocols may be interior or exterior. Conventionally, interior routing protocols are used for determining routes within a routing domain. Examples of interior routing protocols are Routing Information Protocol (RIP) and Open Shortest Path First (OSPF). Exterior routing protocols exchange routing information between routing domains. Examples of exterior routing protocols are Border Gateway Protocol (BGP) and Exterior Gateway Protocol (EGP).
OSPF is a unicast routing protocol that requires each router in a network to be aware of all available links in the network. OSPF calculates routes from each router running the protocol to all possible destinations in the network. Intermediate System to Intermediate System (IS—IS) is an OSI link-state hierarchical routing protocol based on DECnet Phase V routing, whereby ISs (routers) exchange routing information based on a single metric, to determine network topology.
BGP performs interdomain routing in TCP/IP networks. As an exterior gateway protocol (EGP), BGP performs routing between multiple routing domains and exchanges routing and reach ability information with other BGP systems. Each BGP router maintains a routing database that lists all feasible paths to a particular network. The router does not refresh the routing database, however. Instead, routing information received from peer routers is retained until an incremental update is received. BGP devices exchange routing information upon initial data exchange and after incremental updates. When a router first connects to the network, BGP routers exchange their entire BGP routing tables.
In order to update their routing databases, routers send and receive information regarding network topology. Examples of such information include routing update messages, and link-state advertisements. By communicating with other routers in this way, each router obtains a routing database that defines the current topology of the network of which it is a part, enabling determination of optimal routing path.
Entries are added to and removed from the route database either by the user (e.g., a network administrator) in the form of static routes, or by various dynamic routing protocol tasks. In dynamic routing, routes are updated by software running in the router. The routing database defines a mapping from destination address to logical (output) interface, enabling the router to forward packets along the best route toward their destination. The route database is also the principal medium used to share routes among multiple active routing protocols. Thus, the routing database comprises an essential entity at the heart of every router.
Typically, two or three routing protocols may be active in any one router. The routing database as such is a superset of the set of routes actually used for forwarding packets. This is due, in part, to the fact that different routing protocols compute their preferred routes independently of each other, based on different metrics. Only when all route entries generated by the full complement of routing protocols are shared in the routing database, or route table, can the best routes be selected. The result of this selection is a subset of the routing database commonly referred to as the forwarding table. The forwarding table can be considered a filtered view of the routing database. The forwarding table is used by all entities of the router that have to forward packets in and out of the router.
In a BGP system known to the inventors, change information to entries in a routing table are processed and forwarded to peers running BGP protocol. A BGP module running in a router generally comprises a receiving module for receiving an update and a consumer or peer module for propagating valid changed entries to BGP peers. In basic practice, table entry changes comprise updates of better routes or new route additions and deletions. The transactions or propagations of this information are called notifications. Notifications are queued and sent to peers to update their tables. Pluralities of notifications are kept in what is termed a notification list (NL). A convention known as a network-layer-routing-information (NLRI) is a structure that represents a network prefix for layer 3 routing purposes. A convention known as a network layer route entry (NLRE), in BGP, is a BGP route associated with a particular NLRI. A NLRI can have multiple NLRE associated with it. Optimally, a best NLRE is selected via processing for a NLRI from all of the reachable NLRE listed in the table for that prefix.
A NLRI is marked “changed” if it's best NLRE changes. A NLRI is marked deleted if it is found that there are no longer any reachable NLREs within its network prefix list of entries. A NLRI that has a NLRE added or deleted is considered a change notification (CN). A list of the NLRIs marked changed or deleted but that have not yet been peer-processed is considered to comprise an NLRI outbound queue list or the notification list (NL) introduced above. That is to say that the unprocessed NLRIs are queued for processing and propagation to peers in a FIFO outbound queue.
In a current process known to the inventors, all NLRIs from a routing table that are marked changed or deleted are queued and reviewed. If valid they are converted into outbound data packets and buffered for transmission to peers on a per-peer basis according to a timed advertising interval unique to each peer. The advertising interval is the minimum allowable time period per peer that can expire before a next update of a same prefix or NLRI.
A problem with the way the art is currently practiced is that BGP places every NLRI into outbound packet buffers on a per-peer basis. This means that significant packet buffering circuitry must be provided at the transmit or server side of the transactions. Change notifications are copied multiple times for multiple peers. Moreover peers are forced to accept packets only as fast as the BGP module can create (replicate) and send them. In the event of a busy peer, no inbound data can be processed, which may lead to packet overflow at the outbound packet buffer of that the router on the sender side. The current (and inefficient) way to handle this problem is to slow every peer down in a peer group to the rate of the slowest peer.
Another problem with the way the art is currently practiced is that there is no priority scheme available. For example, a NLRI marked deleted should logically have a higher priority than one marked changed, as it is important to remove non-usable entries from all peers promptly.
What is clearly needed is a method and apparatus that provides a virtual buffer for buffering one set of NLRIs that can be processed simultaneously by all of the peers. A method and apparatus such as this would enable reduction of outbound packet buffering and would allow for the frequency of updates to adjust to the speed at which they can be processed on the receiver end.